Skip to main content

17677 - [1차] 뉴스 클러스터링

info

풀이 키워드

스포주의

해시


풀이 코드

info
  • 메모리: 92100 KB
  • 시간: 14 ms
import java.util.*;

class Solution {
public int solution(String str1, String str2) {
// to lowercase
str1 = str1.toLowerCase();
str2 = str2.toLowerCase();

// set
Map<String, Integer> A = new HashMap<>();
Map<String, Integer> B = new HashMap<>();
Map<String, Integer> I = new HashMap<>();
Map<String, Integer> U = new HashMap<>();

// init set
char[] s1Arr = str1.toCharArray();
char[] s2Arr = str2.toCharArray();

for (int i = 0; i < str1.length()-1; ++i)
if ('a' <= s1Arr[i] && s1Arr[i] <= 'z' && 'a' <= s1Arr[i+1] && s1Arr[i+1] <= 'z')
A.merge("" + s1Arr[i] + s1Arr[i+1], 1, Integer::sum);

for (int i = 0; i < str2.length()-1; ++i)
if ('a' <= s2Arr[i] && s2Arr[i] <= 'z' && 'a' <= s2Arr[i+1] && s2Arr[i+1] <= 'z')
B.merge("" + s2Arr[i] + s2Arr[i+1], 1, Integer::sum);

// get intersection
for (String k : A.keySet()) {
if (B.containsKey(k)) I.put(k, Math.min(A.get(k), B.get(k)));
}

// get union
for (String k : A.keySet()) {
U.put(k, B.containsKey(k) ? Math.max(A.get(k), B.get(k)) : A.get(k));
}
for (String k : B.keySet()) {
if (!U.containsKey(k)) U.put(k, B.get(k));
}

int a = I.values().stream().mapToInt(i->i).sum();
int b = U.values().stream().mapToInt(i->i).sum();

if (b == 0) return 65536;
return (int) (65536 * (double) a / b);
}
}

풀이 해설

해시맵을 이용하여 다중집합의 교집합, 합집합을 구하고, 최종적으로 자카드 유사도를 계산하는 문제이다.


✖️ 교집합

A, B 양 쪽에 모두 존재할때만 min value를 넣는다.

for (String k : A.keySet()) {
if (B.containsKey(k)) I.put(k, Math.min(A.get(k), B.get(k)));
}

➕ 합집합

  1. A에만 있으면 A value로 넣는다.
  2. A, B 모두에 있으면 max value로 넣는다.
  3. B에 있으면서 1,2에서 확인하지 않은(=B에만 있는) 값은 B value로 넣는다.
for (String k : A.keySet()) {
U.put(k, B.containsKey(k) ? Math.max(A.get(k), B.get(k)) : A.get(k));
}
for (String k : B.keySet()) {
if (!U.containsKey(k)) U.put(k, B.get(k));
}

메모

  • 무난한 난이도
  • 막줄 a, b 네이밍 별로인듯.. ni, nu가 직관적이고 나을듯